//
//  MaxCoins.swift
//  LeetCodeSummary
//
//  Created by 彭西西 on 2020/7/19.
//  Copyright © 2020 WangYonghe. All rights reserved.
//  312. 戳气球

import UIKit

/*
 312. 戳气球

 有 n 个气球，编号为0 到 n-1，每个气球上都标有一个数字，这些数字存在数组 nums 中。

 现在要求你戳破所有的气球。如果你戳破气球 i ，就可以获得 nums[left] * nums[i] * nums[right] 个硬币。 这里的 left 和 right 代表和 i 相邻的两个气球的序号。注意当你戳破了气球 i 后，气球 left 和气球 right 就变成了相邻的气球。

 求所能获得硬币的最大数量。

 说明:

 你可以假设 nums[-1] = nums[n] = 1，但注意它们不是真实存在的所以并不能被戳破。
 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100
 示例:

 输入: [3,1,5,8]
 输出: 167
 解释: nums = [3,1,5,8] --> [3,5,8] -->   [3,8]   -->  [8]  --> []
      coins =  3*1*5      +  3*5*8    +  1*3*8      + 1*8*1   = 167
 */

/*
 为了方便处理，我们对 nums 数组稍作处理，将其两边各加上题目中假设存在的nums[−1] 和 nums[n] ，并保存在val 数组中，即val[i]=nums[i−1] 。之所以这样处理是为了处理nums[−1] ，防止下标越界。

 令dp[i][j] 表示填满开区间(i,j) 能得到的最多硬币数，那么边界条件是i≥j−1，此时有dp[i][j]=0。

 可以写出状态转移方程：
        j-1
        MAX val[i]*val[k]*val[j]+dp[i][k]+dp[k][j]     i < j-1
        k=i+1
 
        0                                              i >= j-1
 
 最终答案为dp[0][n+1]
 
 */

class MaxCoins: NSObject {
    func maxCoins(_ nums: [Int]) -> Int {
        if nums.count == 0 {
            return 0
        }
        
        let n = nums.count
        
        
        var rec = [[Int]](repeating: [Int](repeating: 0, count: n+2), count: n+2)
        var val = [Int](repeating: 0, count: n+2)
        val[0] = 1
        val[n+1] = 1
        
        for index in 1 ... n{
            val[index] = nums[index-1]
        }
        
        for i in (0 ... n-1).reversed(){
            for j in i+2 ... n+1 {
                for k in i+1 ..< j{
                    var sum = val[i]*val[k]*val[j]
                    sum += rec[i][k]+rec[k][j]
                    rec[i][j] = max(rec[i][j], sum)
                }
            }
        }
        
        return rec[0][n+1]
    }
    /*
     时间复杂度：O(n3)，其中 n 是气球数量。状态数为n2，状态转移复杂度为O(n)，最终复杂度为O(n2*n) = O(n3)
     空间复杂度：O(n3)，其中 n 是气球数量。
     */
}
